/**
 * @作者 zxy
 * @时间 2023-04-25 12:32
 * @说明 1385. 两个数组间的距离值
 * 给你两个整数数组 arr1 ， arr2 和一个整数 d ，请你返回两个数组之间的 距离值 。
 * <p>
 * 「距离值」 定义为符合此距离要求的元素数目：对于元素 arr1[i] ，不存在任何元素 arr2[j] 满足 |arr1[i]-arr2[j]| <= d 。
 * 示例 1：
 * 输入：arr1 = [4,5,8], arr2 = [10,9,1,8], d = 2
 * 输出：2
 */
public class Solution {
    /**
     * 执行用时：2 ms, 在所有 Java 提交中击败了97.12%的用户
     * 内存消耗：41.4 MB, 在所有 Java 提交中击败了6.92% 的用户
     */
    public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
        int[] rec = new int[6001];
        for (int k : arr2) {
            rec[k + 3000] = 1;
        }
        int resNum = 0;
        int left;
        int right;
        for (int j : arr1) {
            left = right = j + 3000;
            while (true) {
                if (rec[left] == 1 || rec[right] == 1) {
                    if (Math.min(Math.abs(j - left + 3000), Math.abs(j - right + 3000)) > d) {
                        resNum++;
                    }
                    break;
                } else {
                    if (left > 0) left--;
                    if (right < rec.length - 1) right++;
                }
            }
        }
        return resNum;
    }
}
